package com.xaicode.algorithm.leetcode._301_400;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * <a href="https://leetcode-cn.com/problems/intersection-of-two-arrays">两个数组的交集</a>
 *
 * <p>给定两个数组，编写一个函数来计算它们的交集。</p>
 *
 * <p>&nbsp;</p>
 *
 * <p><strong>示例 1：</strong></p>
 *
 * <pre><strong>输入：</strong>nums1 = [1,2,2,1], nums2 = [2,2]
 * <strong>输出：</strong>[2]
 * </pre>
 *
 * <p><strong>示例 2：</strong></p>
 *
 * <pre><strong>输入：</strong>nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * <strong>输出：</strong>[9,4]</pre>
 *
 * <p>&nbsp;</p>
 *
 * <p><strong>说明：</strong></p>
 *
 * <ul>
 * 	<li>输出结果中的每个元素一定是唯一的。</li>
 * 	<li>我们可以不考虑输出结果的顺序。</li>
 * </ul>
 *
 * @author beborn xaicode@sina.com
 */
public class _349_Easy_IntersectionOfTwoArrays {

    public static void main(String[] args) {

    }

    /**
     * 执行耗时:2 ms,击败了96.40% 的Java用户
     * 内存消耗:38.5 MB,击败了69.87% 的Java用户
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        for (int num : nums1) {
            set1.add(num);
        }
        for (int num : nums2) {
            set2.add(num);
        }
        if (set1.size() > set2.size()) {
            Set<Integer> temp = set1;
            set1 = set2;
            set2 = temp;
        }
        List<Integer> result = new ArrayList<>();
        for (Integer cur : set1) {
            if (set2.contains(cur)) {
                result.add(cur);
            }
        }
        int[] arr = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            arr[i] = result.get(i);
        }
        return arr;
    }

    /**
     * 执行耗时:2 ms,击败了96.40% 的Java用户
     * 内存消耗:38.5 MB,击败了76.16% 的Java用户
     */
    public int[] intersection1_1(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        for (int num : nums1) {
            set1.add(num);
        }
        for (int num : nums2) {
            set2.add(num);
        }
        if (set1.size() > set2.size()) {
            Set<Integer> temp = set1;
            set1 = set2;
            set2 = temp;
        }
        Set<Integer> result = new HashSet<>();
        for (Integer cur : set1) {
            if (set2.contains(cur)) {
                result.add(cur);
            }
        }
        int[] arr = new int[result.size()];
        int index = 0;
        for (Integer num : result) {
            arr[index++] = num;
        }
        return arr;
    }

    /**
     * 执行耗时:3 ms,击败了81.29% 的Java用户
     * 内存消耗:38.3 MB,击败了94.43% 的Java用户
     */
    public int[] intersection2(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        for (int num : nums1) {
            set1.add(num);
        }
        for (int num : nums2) {
            set2.add(num);
        }
        return getIntersection2(set1, set2);
    }

    private int[] getIntersection2(Set<Integer> set1, Set<Integer> set2) {
        if (set1.size() > set2.size()) {
            return getIntersection2(set2, set1);
        }
        Set<Integer> intersectionSet = new HashSet<Integer>();
        for (int num : set1) {
            if (set2.contains(num)) {
                intersectionSet.add(num);
            }
        }
        int[] intersection = new int[intersectionSet.size()];
        int index = 0;
        for (int num : intersectionSet) {
            intersection[index++] = num;
        }
        return intersection;
    }

}
